package cn.jzq.sort;

import cn.jzq.util.ArrayTool;

import java.util.Arrays;


public class BubbleSort
{
	/**
	 *  普通冒泡排序
     *  时间复杂度 O(n^2)
     *  插入排序的速度直接是逆序对的个数，而冒泡排序中执行“交换“的次数是逆序对的个数，因此冒泡排序执行的时间至少
     *  是逆序对的个数，因此插入排序的执行时间至少比冒泡排序快
	 */
	public static void bubbleSort(Integer[] array)
	{
		for (int i = 0; i < array.length - 1; i++)
		{
			for (int j = array.length - 1; j > i; j--)
			{
				if (array[j] <= array[j - 1])
				    ArrayTool.swap(array, j - 1, j);
			}
		}
	}

    public static void main(String[] args)
    {
        Integer[] arr = ArrayTool.getRandomArray(123,10);
        System.out.println(ArrayTool.toString(arr));

        bubbleSort(arr);
        System.out.println("sorted array : " + ArrayTool.toString(arr));
    }

}
